package com.cdream.basic.algorithm.leetcode.dp;

import java.util.Arrays;

/**
 * @author cdream
 * @date 6/12/21
 */
public class Question1449 {
    public static void main(String[] args) {
        double mod = 1e9 + 7;
        System.out.println(1 % mod);
        // System.out.println(new Question1449().largestNumber(new int[]{4, 3, 2, 5, 6, 7, 2, 5, 5}, 9));
    }

    public String largestNumber(int[] cost, int target) {
        // target为i的情况下最大的String
        // 避免非法转移
        String[] dp = new String[target + 1];
        Arrays.fill(dp, "#");
        dp[0] = "";
        for (int i = 1; i <= cost.length; i++) {
            int c = cost[i - 1];// 成本为c，i为值
            for (int j = 1; j <= target; j++) {
                if (c <= j && !"#".equals(dp[j - c])) {
                    // 上一层的j 和 本层的j-i,可重复选择的结果
                    dp[j] = maxString(dp[j], i + dp[j - c]);
                }
            }
        }
        return "#".equals(dp[target]) ? "0" : dp[target];

    }

    private String maxString(String s, String mix) {
        if (s.length() != mix.length()) {
            return s.length() > mix.length() ? s : mix;
        }
        char[] chars1 = s.toCharArray();
        char[] chars2 = mix.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (chars1[i] > chars2[i]) {
                return s;
            } else {
                return mix;
            }
        }
        return s;
    }


}
